package algorithm.impl;

import algorithm.Sort;
import static algorithm.SortHelper.*;

/**
 * 冒泡排序<br />
 * O(n^2)时间<br />
 */
public class BubbleSort implements Sort {
    public <T extends Comparable> void sort(T[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if(!less(arr[j], arr[j+1])){
                    swap(arr, j , j+1);
                }
            }
        }
    }
    public static void main(String[] args) {

        BubbleSort sort = new BubbleSort();
        Integer[] integers = new Integer[]{10, 9, 8, 7,6,5,4,3,2,1};
        testSort("选择排序", sort, integers);

        Float[] floats = new Float[]{4.4f, 3.3f, 2.2f, 1.1f};
        testSort("选择排序", sort, floats);

        Character[] characters = new Character[]{'z', 'y', 'x', 'w', 'v', 'u'};
        testSort("选择排序", sort, characters);

        String[] strings = new String[]{"D", "C", "B", "A"};
        testSort("选择排序", sort, strings);

        int n = 10000;
        Integer[] array = generateRandomArray(n, 0, n);
        testSort("选择排序", sort, array);

        //近似排序的情况下, 速度很快
        array = generateNearlyOrderedArray(n, n/10);
        testSort("选择排序", sort, array);

    }

}
